package com.algorithm5;

import java.util.Arrays;

public class QuickSort {

    public static void quickSort(int[] array,int start,int end){
        if(start >= end)
            return;
        int pivot = partion(array,start,end);
        quickSort(array,start,pivot-1);
        quickSort(array,pivot+1,end);
        //System.out.println("pivot="+pivot+"-->array:"+ Arrays.toString(array));

    }

    public static  int partion(int[] array,int p,int r){
        int pivot = r;
        int i=p;
        for(int j=p;j<r;j++){
            if(array[j]<array[r]){
                swap(array,i,j);
                i++;
            }
        }
        swap(array,i,pivot);
        System.out.println("pivot="+array[pivot]+"-->array:"+ Arrays.toString(array));
        return i;
    }

    public static void swap(int[] array,int i,int j){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    public static void main(String[] args){
        int[] array = new int[]{4,3,5,8,9,7,10,6,1,2};
        System.out.println("array:"+ Arrays.toString(array));
        quickSort(array,0,array.length-1);
        System.out.println("sorted array:"+ Arrays.toString(array));
    }
}
